package everydayone.lfuCache;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * @Date 2020/04/05
 * @author 王光浩
 * @Thinking 使用双向链表来实现，使用一个双向链表来存储每一个频次对应的 key，并且保存一个变量来记录最小出现次数，
 * 			  然后我们需要删除最近最少被使用的 key-value时，直接可以根据最小出现次数来获取对应的双向链表，然后我们删除
 * 			 双向链表的第一个即可，这样get和put的时间复杂度就是O（1）
 * @ 键值对：使用HashMap存储
 * @ 出现次数：使用HashMap存储，key为关键字，value为可以的出现次数
 * @ 优先关系：使用一个HashMap存储，key为出现的频次，value为一个LinkedHashSet<Integer>,value中保存着该频次的所有key，
 * 			   按照被使用顺序保存的，最久未被使用的存储在第一个，最近被使用的存储在最后一个
 * @ get——更新对应key的出现次数，同时更新它的优先关系，将原本key的位置，移动到原本出现次数+1的LinkedHasSet的末端。
 * @ put——如果容量为0，则返回，如果key已经存在，则更新即可（如同get），否则如果当前容量达到最大值，则使用min获取最小出现
 * 		  频数的LinkedHashSet，然后删除第一个，随后将需要put的键值对put即可，否则直接put。
 * @Analysis 时间复杂度O（1），空间复杂度O（n）
 */
public class MyMethodTwo {
	private HashMap<Integer,Integer> cache;               //存储键值对
	private HashMap<Integer,Integer> freq;                //存储键频次对
	private HashMap<Integer,LinkedHashSet<Integer>> help; //存储每一个频次的所有键
	private int size;                                     //存储当前容量
	private int capacity2;								  //总容量
	private int min=1;
	public MyMethodTwo(int capacity) {
		cache=new HashMap<>(capacity);
		freq=new HashMap<>(capacity);
		help=new HashMap<>();
		size=0;
		capacity2=capacity;
    }
    
    public int get(int key) {
    	if(!cache.containsKey(key))return -1;
    	reflashFreq(key);
    	return cache.get(key);
    }
    
    public void put(int key, int value) {
    	if(capacity2==0)return;
    	if(cache.containsKey(key)) {
    		reflashFreq(key);
    		cache.put(key, value);
    	}
    	else {
    		if(size>=capacity2) {
    			remove();
    			size++;
    		}
    		//将元素加入到对应的数据结构中
    		cache.put(key,value);
    		freq.put(key, 1);
    		if(!help.containsKey(1)) {
    			help.put(1, new LinkedHashSet<Integer>());
    		}
    		help.get(1).add(key);
    		min=1;
    	}
    }
    /**
     * 更新键为 key 的频次
     * @param key
     */
    private void reflashFreq(int key) {
    	int frequent=freq.get(key);
    	freq.put(key, frequent+1);
    	LinkedHashSet<Integer> tem=help.get(frequent);  //获取频次为 frequnet 的所有键值对
    	tem.remove(key);    //删除 key
    	//如果更新的 key 正好是最近最久未被使用的 key
    	if(frequent==min && tem.size()==0)min+=1;
    	//将 key 重新加入 help 中
    	if(!help.containsKey(frequent+1)) {
    		help.put(frequent+1, new LinkedHashSet<Integer>());
    	}
    	help.get(frequent+1).add(key);
    }
    /**
     * 删除最近最少被使用 key
     */
    private void remove() {
    	LinkedHashSet<Integer> tem=help.get(min);  //从当前最小出现次数的队列中删除最近被使用的key
    	int key=tem.iterator().next();
    	tem.remove(key);
    	freq.remove(key);
    	cache.remove(key);
    	size--;
    }
}
